// 543.二叉树的直径
package LeetcodeHot100;


public class Solution543 {
    public int maxDiameter = Integer.MIN_VALUE;

    public int diameterOfBinaryTree(TreeNode root) {
        countDiameter(root);
        return maxDiameter;
    }

    public int countDiameter(TreeNode root) {
        // 空结点
        if (root == null) {
            return 0;
        } else {
            // 计算经过当前结点额直径
            int left = countDiameter(root.left);
            int right = countDiameter(root.right);
            int diameter = left + right;
            // 对比是否为最大直径
            maxDiameter = Math.max(diameter, maxDiameter);
            // 向父结点返回
            return Math.max(left, right) + 1;
        }
    }
}
